package com.itheima.leetcode.od.c.graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * <h3>网格红绿灯最短路径</h3>
 */
public class ShortestPathForGridTrafficLights {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        // 从标准输入读取第一行：grids 地图
        String gridsLine = reader.readLine();
        if (gridsLine == null) {
            return;
        }
        int[][] grids = parseInput(gridsLine);

        // 从标准输入读取第二行：lights 红绿灯信息
        String lightsLine = reader.readLine();
        int[][] lights;
        if (lightsLine != null && !lightsLine.trim().isEmpty()) {
            lights = parseInput(lightsLine);
        } else {
            lights = new int[0][0];
        }

        System.out.println(shortestPathWithTrafficLights(grids, lights));
    }

    public static int shortestPathWithTrafficLights(int[][] grids, int[][] lights) {
        // 检查输入是否为空
        if (grids == null || grids.length == 0 || grids[0].length == 0) {
            return -1;
        }

        // 获取地图的尺寸 m(行数) 和 n(列数)
        int m = grids.length;
        int n = grids[0].length;

        // 边界条件检查：如果起点或终点是障碍物，则无法通行
        if (grids[0][0] == 1 || grids[m - 1][n - 1] == 1) {
            return -1;
        }

        // --- 数据结构初始化 ---

        // 1. 将 lights 列表转换为哈希表 (HashMap)，以坐标元组 (r, c) 为键，等待时间为值。
        //    这样做可以让我们在 O(1) 的时间复杂度内查询任一坐标的等待时间。
        Map<Integer, Integer> lightsMap = new HashMap<>();
        if (lights != null) { // lights 可能为空
            for (int[] light : lights) {
                if (light.length == 3) { // 确保 light 格式正确
                    lightsMap.put(light[0] * n + light[1], light[2]);
                }
            }
        }

        // 2. 初始化 `min_time` 二维数组，用于存储从起点 (0,0) 到达每个坐标 (r,c) 的已知最短时间。
        //    初始时，所有位置都设为无穷大 (Integer.MAX_VALUE), 表示尚未访问或尚未找到路径。
        int[][] minTime = new int[m][n];
        for (int[] row : minTime) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        // 3. 设置起点的初始时间。
        int initialTime = 0;
        // 如果起点 (0,0) 本身就是一个红绿灯，需要加上它的等待时间。
        // .getOrDefault 确保即使 lightsMap 中没有这个键（数据不规范时），也能安全返回0。
        if (grids[0][0] == 2) {
            initialTime += lightsMap.getOrDefault(0 * n + 0, 0);
        }

        // 更新起点在 min_time 数组中的值为其初始时间
        minTime[0][0] = initialTime;

        // 4. 初始化优先队列 (PriorityQueue)，它是一个最小堆。
        //    队列中存储的元素是元组 (时间, 行坐标, 列坐标)。
        //    PriorityQueue 会根据 Cell 类中定义的 compareTo 方法自动排序，
        //    确保我们每次 `poll` 都能取出当前全局路径成本最低的节点。
        PriorityQueue<Cell> pq = new PriorityQueue<>();
        pq.offer(new Cell(initialTime, 0, 0));

        // 定义四个移动方向：右、左、下、上
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        // --- Dijkstra 算法主循环 ---
        // 只要优先队列中还有待处理的节点，就继续搜索。
        while (!pq.isEmpty()) {
            // 5. 从队列中弹出当前具有最小时间的节点。
            //    currentTime: 到达这个 (r,c) 节点的已知最短时间
            //    r, c: 当前节点的坐标
            Cell current = pq.poll();
            int currentTime = current.time;
            int r = current.r;
            int c = current.c;

            // 优化：如果我们之前已经找到了一条更短的路径到达 (r,c)，
            // 那么当前弹出的这个较长的路径就没有必要处理了，直接跳过。
            if (currentTime > minTime[r][c]) {
                continue;
            }

            // 终止条件：如果弹出的节点是终点 (m-1, n-1)，
            // 根据 Dijkstra 算法的性质，我们第一次到达终点时的时间就是全局最短时间。
            if (r == m - 1 && c == n - 1) {
                return currentTime;
            }

            // 6. 遍历当前节点的所有邻居节点。
            for (int[] dir : directions) {
                // 计算邻居的坐标
                int nr = r + dir[0];
                int nc = c + dir[1];

                // 检查邻居坐标是否合法：
                // a. 是否在地图边界内 (0 <= nr < m and 0 <= nc < n)
                // b. 是否不是障碍物 (grids[nr][nc] != 1)
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grids[nr][nc] != 1) {

                    // --- 计算到达邻居的成本 ---

                    // a. 移动成本：从一个单元格到相邻单元格固定需要 1 秒。
                    int timeToReachNeighbor = currentTime + 1;

                    // b. 等待成本：如果邻居是一个红绿灯，需要加上其等待时间。
                    int waitTimeAtNeighbor = 0;
                    if (grids[nr][nc] == 2) {
                        waitTimeAtNeighbor = lightsMap.getOrDefault(nr * n + nc, 0);
                    }

                    // c. 总成本：到达邻居并完成等待后的总时间
                    int totalTimeAtNeighbor = timeToReachNeighbor + waitTimeAtNeighbor;

                    // 7. 松弛操作 (Relaxation)：
                    //    如果通过当前节点 (r,c) 到达邻居 (nr,nc) 的总时间
                    //    比 `min_time` 中记录的到达 (nr,nc) 的时间更短...
                    if (totalTimeAtNeighbor < minTime[nr][nc]) {
                        // ...就更新 `min_time` 数组中的最短时间...
                        minTime[nr][nc] = totalTimeAtNeighbor;
                        // ...并将这个新的、更优的路径节点加入优先队列。
                        pq.offer(new Cell(totalTimeAtNeighbor, nr, nc));
                    }
                }
            }
        }

        int finalTime = minTime[m - 1][n - 1];

        // 检查终点的最短时间是否仍然是无穷大。如果是，返回-1；否则，返回计算出的最短时间（转为整数）。
        return finalTime != Integer.MAX_VALUE ? finalTime : -1;
    }

    // 将输入的字符串 (例如 "[[1,2],[3,4]]") 解析为 Java 的二维数组。
    private static int[][] parseInput(String line) {
        // 如果输入为空或无效，返回一个空数组
        if (line == null || line.length() < 4) {
            return new int[0][0];
        }

        // 去掉最外层的 "[[...]]" 的括号
        String content = line.substring(2, line.length() - 2);

        // 按行 "],[", 分割字符串
        String[] rowsStr = content.split("\\],\\s*\\[");

        // 如果分割后没有内容，说明可能是空数组 "[]" 或 "[[]]"
        if (rowsStr.length == 0 || rowsStr[0].isEmpty()) {
            return new int[0][0];
        }

        // 创建一个列表来存储解析出的每一行
        List<int[]> rowsList = new ArrayList<>();

        for (String rowStr : rowsStr) {
            // 按逗号分割每一行中的数字
            String[] numsStr = rowStr.split(",");
            int[] row = new int[numsStr.length];
            for (int i = 0; i < numsStr.length; i++) {
                // 将字符串数字转换为整数
                row[i] = Integer.parseInt(numsStr[i].trim());
            }
            rowsList.add(row);
        }

        // 将列表转换为二维数组并返回
        return rowsList.toArray(new int[0][]);
    }

    static class Cell implements Comparable<Cell> {
        int time;
        int r;
        int c;

        public Cell(int time, int r, int c) {
            this.time = time;
            this.r = r;
            this.c = c;
        }

        @Override
        public int compareTo(Cell other) {
            return Integer.compare(this.time, other.time);
        }
    }
}